namespace PF {
    export class AStarFinder {
        heuristic: any;
        weight: number;
        diagonalMovement: DiagonalMovement;
        constructor(opt: IAStarOptions) {
            opt = opt || {};
            this.heuristic = opt.heuristic || Heuristic.manhattan;
            this.weight = opt.weight || 1;
            this.diagonalMovement = opt.diagonalMovement;
            if (!this.diagonalMovement) {
                if (!opt.allowDiagonal) {
                    this.diagonalMovement = DiagonalMovement.Never;
                } else {
                    if (opt.dontCrossCorners) {
                        this.diagonalMovement = DiagonalMovement.OnlyWhenNoObstacles;
                    } else {
                        this.diagonalMovement = DiagonalMovement.IfAtMostOneObstacle;
                    }
                }
            }

            if (this.diagonalMovement === DiagonalMovement.Never) {
                this.heuristic = opt.heuristic || Heuristic.manhattan;
            } else {
                this.heuristic = opt.heuristic || Heuristic.octile;
            }
        }

        findPath(startX: number, startY: number, endX: number, endY: number, grid: Grid) {
            var openList = new Heap<Node>(function (nodeA, nodeB) {
                return nodeA.f - nodeB.f;
            }),
                startNode = grid.getNodeAt(startX, startY),
                endNode = grid.getNodeAt(endX, endY),
                heuristic = this.heuristic,
                diagonalMovement = this.diagonalMovement,
                weight = this.weight,
                abs = Math.abs, SQRT2 = Math.SQRT2,
                node, neighbors, neighbor, i, l, x, y, ng;

            // set the `g` and `f` value of the start node to be 0
            startNode.g = 0;
            startNode.f = 0;

            // push the start node into the open list
            openList.push(startNode);
            (<any>startNode).opened = true;

            // while the open list is not empty
            while (!openList.empty) {
                // pop the position of node which has the minimum `f` value.
                node = openList.pop();
                node.closed = true;

                // if reached the end position, construct the path and return it
                if (node === endNode) {
                    return Util.backtrace(endNode);
                }

                // get neigbours of the current node
                neighbors = grid.getNeighbors(node, diagonalMovement);
                for (i = 0, l = neighbors.length; i < l; ++i) {
                    neighbor = neighbors[i];

                    if (neighbor.closed) {
                        continue;
                    }

                    x = neighbor.x;
                    y = neighbor.y;

                    // get the distance between current node and the neighbor
                    // and calculate the next g score
                    ng = node.g + ((x - node.x === 0 || y - node.y === 0) ? 1 : SQRT2);

                    // check if the neighbor has not been inspected yet, or
                    // can be reached with smaller cost from the current node
                    if (!neighbor.opened || ng < neighbor.g) {
                        neighbor.g = ng;
                        neighbor.h = neighbor.h || weight * heuristic(abs(x - endX), abs(y - endY));
                        neighbor.f = neighbor.g + neighbor.h;
                        neighbor.parent = node;

                        if (!neighbor.opened) {
                            openList.push(neighbor);
                            neighbor.opened = true;
                        } else {
                            // the neighbor can be reached with smaller cost.
                            // Since its f value has been updated, we have to
                            // update its position in the open list
                            openList.updateItem(neighbor);
                        }
                    }
                }
            }
            return [];
        }
    }
}

interface IAStarOptions {
    allowDiagonal?:boolean;
    dontCrossCorners?: boolean;
    /**允许对角线移动。 */
    diagonalMovement?: PF.DiagonalMovement;
    heuristic?: Function;
    weight?: number;
}